import java.util.ArrayList;
import java.util.List;
public class MyBinaryTree {
        static class TreeNode {
            public char val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(char val) {
                this.val = val;
            }
        }
        public TreeNode createBinaryTree() {
            TreeNode nodeA = new TreeNode('A');
            TreeNode nodeB = new TreeNode('B');
            TreeNode nodeC = new TreeNode('C');
            TreeNode nodeD = new TreeNode('D');
            TreeNode nodeE = new TreeNode('E');
            TreeNode nodeF = new TreeNode('F');
            TreeNode nodeG = new TreeNode('G');
            TreeNode nodeH = new TreeNode('H');
            nodeA.left = nodeB;
            nodeA.right = nodeC;
            nodeB.left = nodeD;
            nodeB.right = nodeE;
            nodeE.right = nodeH;
            nodeC.left = nodeF;
            nodeC.right = nodeG;
            return nodeA;
        }
        //前序遍历
        public void preOrder(TreeNode root) {
            if(root == null) return;
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        //中序遍历
        public void inOrder(TreeNode root) {
            if(root == null) return;
            preOrder(root.left);
            System.out.print(root.val+" ");
            preOrder(root.right);
        }
        //后序遍历
        public void postOrder(TreeNode root) {
            if(root == null) return;
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.val+" ");
        }
        public static int nodeSize;

        /**
         * 获取树中节点的个数：遍历思路
         */
        void size(TreeNode root) {
            if(root == null) return;
            nodeSize ++;
            size(root.left);
            size(root.right);
        }

        /**
         * 获取节点的个数：子问题的思路
         *
         * @param root
         * @return
         */
        int size2(TreeNode root) {
            if(root == null) return 0;
            int m = size2(root.left);
            int n = size2(root.right);
            return m + n + 1;
        }


        /*
         获取叶子节点的个数：遍历思路
         */
        public static int leafSize = 0;

        void getLeafNodeCount1(TreeNode root) {
            if(root.right == null && root.left == null) {
                leafSize ++;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }

        /*
         获取叶子节点的个数：子问题
         */
        int getLeafNodeCount2(TreeNode root) {
            if(root == null) return 0;
            if(root.left == null && root.right == null) {
                return 1;
            }
            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }

        /*
        获取第K层节点的个数
         */
        int getKLevelNodeCount(TreeNode root, int k) {
            if(k == 1) {
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
        }

        /*
         获取二叉树的高度
         时间复杂度：O(N)
         */
        int getHeight(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            return left > right ? left + 1 : right + 1;
        }


        // 检测值为value的元素是否存在
        boolean find(TreeNode root, char val) {
            if(root == null) {
                return false;
            }
            if(root.val == val) {
                return true;
            }
            boolean left = find(root.left,val);
            if(left == true) {
                return true;
            }
            boolean right = find(root.right,val);
            if(right == true) {
                return true;
            }
            return false;
        }

    }
